1. Field of the Invention
The present invention relates to Medium Access Control (MAC) sublayer protocols for network interfaced systems, and more particularly, to network systems requiring collision resolution mediation.
2. Present State of the Art
In any network in which multiple hosts are connected to a fixed single shared communications channel, there must be a method to resolve which host obtains use of a channel when there is contention. In a single shared communications channel system, data sent by one host will be received by all other hosts. However, if two different hosts attempt to transmit data simultaneously, there is a collision, and the data is lost. The various methods to resolve contests between the hosts and for recovering from collisions are called Medium Access Control (MAC) sublayer protocols.
Protocols in which multiple hosts listen for a carrier (i.e. a transmission) to determine whether the channel is currently busy are called Carrier Sense Multiple Access (CSMA) protocols. By waiting until the channel is free to begin transmitting, some collisions are avoided. Many industry standards use CSMA protocols, the most popular standard being Ethernet, which uses a CSMA/CD protocol (CD standing for Collision Detection).
The CSMA/CD protocol works as follows: a station designed to transmit senses a medium. If the medium is busy (i.e. some other station is transmitting) then the station defers its transmission to a later time. If the medium is sensed free then the station is allowed to transmit. This is very effective when the medium is not heavily loaded, since it allows stations to transmit with minimum delay. But there is always a chance of multiple stations simultaneously sensing the medium as being free and transmitting at the same time, causing a collision. The collision is detected by the stations transmitting since they listen to the medium while they transmit to ensure that they are the only station transmitting at that time. If the stations hear their own transmission returning in a garbled form, as would happen if some other station had begun to transmit its own message at the same time, then they know that a collision occurred.
In the Ethernet case, if such a collision is recognized by the transmitting station, then it enters into a retransmission phase based on an exponential random back-off algorithm. This exponential random back-off algorithm is a method used to dynamically adapt to the number of transmitting stations trying to send data to thereby reduce an overall number of collisions. Essentially, the exponential random back-off algorithm helps to prevent multiple stations from attempting to retransmit simultaneously at predetermined transmission delay intervals. The exponential random back-off algorithm achieves this by using a pseudorandom delay mechanism to enforce a collision back-off interval before retransmissions occur (discussed hereinafter as BEB).
Another protocol using the MAC layer is the 802.11 LAN standard, which is based on a cellular architecture where the system is subdivided into cells. Each cell (called Basic Service Set, or BSS, in 802.11 nomenclature) is controlled by a Base Station (called Access Point or, in short AP). Much like Ethernet, the 802.11 LAN standard relies upon a protocol to ensure that collisions occur infrequently.
The Institute of Electrical and Electronics Engineers (IEEE) has produced several standards for MAC protocols. IEEE standard 802.3 has been universally adopted for the CSMA/CD protocol. In the 802.3 standard, each host that has data to transmit waits until it detects an idle channel, and then begins transmitting.
The 802.3 standard uses the Binary Exponential Backoff (BEB) method to dynamically adapt to the number of hosts trying to send, thereby effectively reducing the probability of a collision. If a host detects collision, it waits a random integer number of “slot times” before repeating the cycle. A slot time represents the minimum period of time that a transmitting station needs access to a medium to send a smallest legal packet size. In the standard, a slot time is defined as the time required to transmit 512 bits over the network and is based upon the maximum distance between any two stations on a network. This value is determined by the worst case round trip propagation delay between hosts allowed by standard 802.3 for 10 Mbps networks, and has been preserved in the new standard for 100 Mbps networks.
If two different hosts pick up the same random number of slot times, a collision will occur. The maximum random number increases as the number of collisions increases. In the BEB method, the random number is between zero and 2min(n, 10)−1, where the counter n is the number of collisions experienced by a packet. Therefore, after the first collision, the host waits zero or one slot time. After the second collision, the host waits zero, one, two or three slot times. However, after ten collisions, the maximum random number is frozen at 1023. In addition, after 16 collisions, a controller reports a failure back to the host. Following the successful transmission, the counter n in the successful host is reset to zero.
The MAC sublayer protocol currently used can cause significant performance problems. Since collisions waste channel bandwidth, it is vital that the number of collisions be minimized to decrease the load on the channel. In addition, collisions can generate more collisions through positive feedback when the retransmitted packets compete with later arrivals. In other words, positive feedback occurs when transmitted packets collide and at a later time compete to retransmit with new stations contending for channel availability. This phenomenon tends to heavily load the channel with time. A protocol may be described as stable if it avoids the positive feedback effect. Unfortunately, it is not clear whether the BEB method is stable.
Even if the BEB method is stable, the dynamics represent a poor scheduling discipline. The BEB method results in a reverse lottery in which certain packets are selected for exceptionally long delays, while most other packets are transmitted as soon as they reach the head of the transmit queue.
It is important to distinguish the perceptions of the service provider from the user. The primary concern of the service provider is throughput; whenever there is data in the system in need of transmission, the network should be engaged in delivering it. The users, on the other hand, are primarily concerned with delay. Delay consists both of waiting time, the time that elapses from generation of a data packet to its arrival at the head of the transmit queue, and access time, the time that a data packet spends at the head of the transmit queue. Human users have a strong dislike for unpredictability. In many applications, such as a voice or video, delay variance is as important as the average delay.
With BEB, the collision counter (equal to the number n above) of a given host is updated only in response to actual transmission attempts by the host. Consider several active hosts each with several data packets in queue. Once there is a successful packet transmission, only the “winner” will reset its collision counter to zero. First, the winning host is free to transmit its next packet immediately, while other hosts may have a retry time that is longer than the transmission packet time. Second, at the next collision, the winner randomly selects its retry time from the smallest possible interval, whereas other hosts are randomized in retry times of a much larger interval. Therefore, the first winning host is likely to capture the network repeatedly until its transmit queue is empty. This is called the “capture effect.” Those hosts which have transmitted recently are about one-hundred times more likely to acquire the channel than others. This “last in, first out” system results in unacceptable variations in the delay time.
Modifications to BEB have been proposed in order to eliminate the unfairness of the capture effect in the standard protocol, but their effectiveness has been found to be limited.